1. Technical Field
The present invention relates to circuit design and verification of circuits. More particularly the present invention relates to interconnection circuit modeling. Still more particularly the present invention relates to computing moments associated with circuits in an interconnect circuit.
2. Description of Related Art
Interconnect effects are critically important in the design and verification of integrated circuits. On-chip interconnects are typically modeled by linear resistive (R) and capacitive (C) elements. In some cases, very few global nets may also include inductive (L) elements. With the scaling of the Back-End-Of-the-Line (BEOL) interconnect processes, the effect of interconnect on circuit performance continues to increase. In case of global nets (i.e., nets connecting one macro to another macro), the interconnect delay can typically be much greater than the logic delay. Even among nets within a macro, the interconnect delay can constitute a significant portion of the path delay (i.e., typically up to 25%).
Interconnect modeling is typically performed through a layout-based extraction procedure. Extracted data from a microprocessor may require 2-4 gigabytes of storage. Given the massive amount of data generated by parasitic extractors, it is typically not feasible to perform circuit analysis without use of model reduction or other interconnect pruning techniques.
Model reduction takes an original linear circuit and reduces it to a much smaller linear representation while maintaining much of the circuit performance. Model reduction has been an area of considerable research over the last several years, with much of the work originating from Asymptotic Waveform Evaluation (AWE), disclosed by Pillage and Rohrer in xe2x80x9cAsymptotic Waveform Evaluation for Timing Analysisxe2x80x9d, IEEE Trans. Computer Aided Design, 9(4):352-366, April 1990. AWE computes the moments of the original circuit and then matches these moments to a reduced-order transfer function using Pade approximation. Along with the moment matching techniques, AWE, and later RICE, disclosed by Ratzlaff and Pillage in xe2x80x9cRICE: Rapid Interconnect Circuit Evaluator using Asymptotic Waveform Evaluationxe2x80x9d, IEEE Transactions on Computer Aided Design, pp. 763-776, June 1994, proposed an efficient way of computing the circuit moments by repeated DC solutions. Typically, RC circuits can be modeled by a handful of moments. RLC and PEEC circuits require much larger numbers of moments, though they are typically not used to model on-chip interconnects. The repeated DC solutions used to compute moments causes the accuracy of the moments to decrease as the number of moments increase. Several techniques, notably using Krylov-subspace methods, were developed to increase the accuracy of the model reduction procedure, as disclosed by Feldmann and Fruend, xe2x80x9cReduced-order modeling of large linear subcircuits via a block Lanczos algorithmxe2x80x9d, Proceedings of ACM/IEEE Design Automation Conference, pp. 474-479, 1995; Kerns, Wemple and Wang, xe2x80x9cStable and Efficient Reduction of Substrate model networks using Congruence Transformsxe2x80x9d, Proceedings of IEEE International Conference on Computer Aided Design, pp. 207-214, November 1995; Gallivan, Grimme and Van Dooren, xe2x80x9cAsymptotic Waveform Evaluation via a Lanczos Methodxe2x80x9d, Applied Mathematics Letters, 7(5):75-80, 1994; Silveria, Kamon, Elfadel and White, xe2x80x9cCoupled circuit-interconnect analysis using Arnoldi-based model order reductionxe2x80x9d, IEEE Transactions on Computer Aided Design, 1995. Krylov-subspace methods can match a much higher number of implicit moments yielding much higher accuracy. These techniques are also more suitable for analyzing the frequency response of linearized analog circuits. Block Krylov-subspace methods were developed to handle multi-port circuits; however, these methods typically work well only when the number of ports is less than ten. Krylov-subspace techniques match the original circuit to a set of state equations that describe the reduced circuit. However, the reduced order state equations may not be passive or realizable. Techniques disclosed in Odabasioglu, Celik and Pileggi, xe2x80x9cPRIMA: Passive Reduced-Order Interconnect Macromodeling Algorithm,xe2x80x9d IEEE Transactions on CAD, pp. 645-654, August 1998; and Kerns et al., xe2x80x9cStable and Efficient Reduction of Substrate model networks using Congruence Transformsxe2x80x9d, extend the Krylov-subspace methods to guarantee the passivity of the reduced order state equations. However, these methods do not guarantee the realizability (i.e., modeling reduced order state equations by linear, passive circuit elements) of the reduced circuit equations. Realizability of the reduced order models has been shown only for single port. circuits, as discussed in O""Brien and Savarino, xe2x80x9cModeling the driving-point characteristics of resistive interconnect for accurate delay estimationxe2x80x9d, Proceedings of IEEE International Conference on Computer Aided Design, pp. 512-515, November 1989; and Freund and Feldmann, xe2x80x9cReduced-Order Modeling of Large Passive Linear Circuits by Means of the SyPVL Algorithm,xe2x80x9d Proceedings of IEEE Conference on Computed Aided Design, November 1996.
Realizable model reduction is particularly useful in interconnect analysis. In a typical design methodology, various circuit analysis and verification procedures (e.g., static timing, dynamic simulation, noise analysis, circuit checking, power analysis, etc.) are performed on the extracted parasitic data. If the model reduction of the parasitic data is not realizable, it produces reduced transfer functions or reduced state equations and not reduced RC circuits. Hence, all downstream circuit simulators and associated programs have to be modified to handle reduced order equations. Realizable reduced models are even more useful when both linear and nonlinear parts of the circuit have to be analyzed together. Furthermore, several circuit analysis programs (like circuit checking) only work if the input is in the form of an RC circuit.
Apart from realizability, another significant problem in interconnect analysis is the large number of ports. For example, RC circuits originating from clock and power distribution networks may have hundreds of ports. In some cases, especially for linear analysis, the prior art approximates these networks with single port networks having linear terminations at the other ports. This approximation to single port networks has the disadvantages of causing a loss in accuracy and difficulty in predicting when the approximation works well. For on-chip interconnects, addressing the need for an increase in the number of ports is often more important than increasing the order of the approximation. On-chip interconnects do not require large numbers of moments to produce accurate results. However, they typically do have large numbers of ports. Model reduction of these circuits yields a dense reduced order model which can be prohibitively expensive to analyze using downstream circuit analysis tools. The matrix factorization of a dense matrix is order O(n3), whereas the matrix factorization of a sparse matrix is order O(n15). For the case of circuits with large numbers of ports, the simulation with reduction may often take longer than simulation without reduction.
The present invention discloses a realizable model reduction and linear circuit partitioning techniques. A multi-port circuit is first partitioned into sets of two-port circuits. This partitioning maintains the spatial sparsity of the original circuit. Each two-port circuit is then reduced to an equivalent and realizable RC circuit. Instead of assuming a transfer function or state equations as the model for the reduced system, a representative RC circuit is assumed as the model for the reduced system. The model reduction procedure consists of computing R and C element values for the assumed reduced order circuit. Closed form expressions are derived to compute the element values. Interconnect reductions of each two-port circuit are reconnected to yield the final reduced circuit. This procedure works exceeding well for most on-chip interconnects. The procedure of the present invention does not handle coupling capacitors.
In a preferred embodiment of the present invention, moments of the transfer function are computed for each two-port network. The moments can be computed by setting appropriate excitation and by performing matrix factorization. However, matrix factorization is superlinear with a number of nodes in the circuit. Path tracing can be modified to handle two-port circuits; however, it still requires an inverse of a smaller matrix. Specifically, a preferred embodiment of the present invention discloses a linear time moment computation method for two-port circuits. This method does not require matrix factorization and instead uses repeated Norton to Thevenin conversions to compute the circuit moments.